#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
//class Solution5
//{
//public:
//    vector<int> path;
//    vector<vector<int>> ret;
//    bool used[8] = { false };
//    vector<vector<int>> permuteUnique(vector<int>& nums)
//    {
//        dfs(nums);
//        return ret;
//    }
//    void dfs(vector<int>& nums)
//    {
//        if (path.size() == nums.size())
//        {
//            ret.push_back(path);
//            return;
//        }
//        unordered_set<int> check;
//        for (int i = 0;i < nums.size();i++)
//        {
//            if (!check.count(nums[i]) && !used[i])
//            {
//                path.push_back(nums[i]);
//                check.insert(nums[i]);
//                used[i] = true;
//            }
//            else continue;
//            dfs(nums);
//            path.pop_back();
//            used[i] = false;
//        }
//    }
//};
class Solution {
public:
    bool row[9][10] = { false };
    bool col[9][10] = { false };
    bool grid[3][3][10] = { false };
    vector<vector<string>> ret;
    int n = 0;
    void solveSudoku(vector<vector<string>>& board)
    {
        for (int i = 0;i < 9;i++)
            for (int j = 0;j < 9;j++)
                if (isdigit(board[i][j][0]))
                {
                    int num = board[i][j][0] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                    n++;
                }
        dfs(board);
        board = ret;
    }
    void dfs(vector<vector<string>>& board)
    {
        if (n == 81)
        {
            ret = board;
            return;
        }
        for (int i = 0;i < 9;i++)
            for (int j = 0;j < 9;j++)
                if (!isdigit(board[i][j][0]))
                {
                    n++;
                    for (int k = 1;k <= 9;k++)
                    {
                        if (col[j][k] || row[i][k] || grid[i / 3][j / 3][k]) continue;
                        char num = k + '0';
                        board[i][j] = num;
                        row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = true;
                        dfs(board);
                        row[i][k] = col[j][k] = grid[i / 3][j / 3][k] = false;
                        if (n == 81) return;
                    }
                }
    }
};
using namespace std;
int main()
{
    vector<vector<string>> vv = {
        {"5","3",".",".","7",".",".",".","."},
        {"6",".",".","1","9","5",".",".","."},
        {".","9","8",".",".",".",".","6","."},
        {"8",".",".",".","6",".",".",".","3"},
        {"4",".",".","8",".","3",".",".","1"},
        {"7",".",".",".","2",".",".",".","6"},
        {".","6",".",".",".",".","2","8","."},
        {".",".",".","4","1","9",".",".","5"},
        {".",".",".",".","8",".",".","7","9"},
    };
    Solution().solveSudoku(vv);
	return 0;
}